package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-24 15:38
 */
public class minDistance72 {

    /**72. 编辑距离
     * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
     * 1、递归：dp(i,j)表示word1[i...0]与word2[j...0]的最小编辑距离
     *       当word1[i]==word2[j],i--,j--什么都不做。直接匹配
     *       else:dp(i,j-1)+1----插入：直接在 s1[i] 插入一个和 s2[j] 一样的字符，那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
     *            dp(i-1,j)+1----删除直接把 s1[i] 这个字符删掉
     *            dp(i - 1, j - 1) + 1---替换
     *
     * 2、dp[i][j]表示s1[0..i] 和 s2[0..j] 的最小编辑距离
     * */
    public int minDistance(String word1, String word2) {
        int m=word1.length(),n=word2.length();
        int[][] dp=new int[m+1][n+1];
        for (int i = 1; i <=m ; i++) {
            dp[i][0]=i;
        }
        for (int i = 1; i <=n ; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    //需要下标向后移一位
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[m][n];
    }
}
